class Solution {

    private HashMap<Integer, Integer> cache = new HashMap<>();

    public int numTrees(int n) {
        if (n <= 1){
            return 1;
        }
        Integer cacheValue = cache.get(n);
        if (cacheValue != null){
            return cacheValue;
        }
        int count = 0;
        for (int i = 1; i <= n; i++) {
            // i 为顶点
            int left = this.numTrees(i - 1);
            int right = this.numTrees(n-i);
            count += left*right;
        }
        cache.put(n, count);
        return count;
    }
}
